/**
 * 队列
1. 用链表实现链队列，支持 enqueue、dequeue、front、rear、isEmpty。
测试用例：enqueue(1,2,3)→front ()=1，rear ()=3→dequeue ()=1→队列剩 [2,3]。
2. 用两个栈实现队列功能（入队→栈 A，出队→栈 B），
测试用例：入队 1→2→3→出队= 1→入队 4→出队 = 2→出队 = 3→出队 = 4。
 */
//2. 用两个栈实现队列功能（入队→栈 A，出队→栈 B），
//测试用例：入队 1→2→3→出队= 1→入队 4→出队 = 2→出队 = 3→出队 = 4。
// 栈的结构体定义（复用之前的栈实现）
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
typedef struct {
    int* data;
    int top;
    int capacity;
} Stack;

// 初始化栈
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    if (stack == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    stack->capacity = capacity;
    stack->top = -1;
    stack->data = (int*)malloc(capacity * sizeof(int));
    if (stack->data == NULL) {
        printf("内存分配失败\n");
        free(stack);
        exit(1);
    }
    return stack;
}

// 栈判空
bool isStackEmpty(Stack* stack) {
    return stack->top == -1;
}

// 栈判满
bool isStackFull(Stack* stack) {
    return stack->top == stack->capacity - 1;
}

// 入栈
void push(Stack* stack, int value) {
    if (isStackFull(stack)) {
        printf("错误：栈已满\n");
        exit(1);
    }
    stack->data[++stack->top] = value;
}

// 出栈
int pop(Stack* stack) {
    if (isStackEmpty(stack)) {
        printf("错误：栈为空\n");
        exit(1);
    }
    return stack->data[stack->top--];
}

// 用两个栈实现的队列结构体
typedef struct {
    Stack* stackA;  // 负责入队
    Stack* stackB;  // 负责出队
} QueueWithTwoStacks;

// 初始化队列
QueueWithTwoStacks* createQueueWithTwoStacks(int capacity) {
    QueueWithTwoStacks* queue = (QueueWithTwoStacks*)malloc(sizeof(QueueWithTwoStacks));
    if (queue == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    queue->stackA = createStack(capacity);
    queue->stackB = createStack(capacity);
    return queue;
}

// 入队操作（直接压入栈A）
void enqueue2(QueueWithTwoStacks* queue, int value) {
    push(queue->stackA, value);
}

// 出队操作（栈B为空时，将栈A所有元素转移到栈B）!!!!!!!!!!!
int dequeue2(QueueWithTwoStacks* queue) {
    // 若栈B为空，将栈A所有元素弹出并压入栈B
    if (isStackEmpty(queue->stackB)) {
        while (!isStackEmpty(queue->stackA)) {
            int value = pop(queue->stackA);
            push(queue->stackB, value);
        }
    }
    // 从栈B弹出元素（即队头元素）
    return pop(queue->stackB);
}

// 释放队列内存
void freeQueueWithTwoStacks(QueueWithTwoStacks* queue) {
    free(queue->stackA->data);
    free(queue->stackA);
    free(queue->stackB->data);
    free(queue->stackB);
    free(queue);
}

// 测试两个栈实现的队列
void testQueueWithTwoStacks() {
    QueueWithTwoStacks* queue = createQueueWithTwoStacks(10);
    
    // 入队 1→2→3
    enqueue2(queue, 1);
    enqueue2(queue, 2);
    enqueue2(queue, 3);
    
    // 出队
    printf("出队 = %d\n", dequeue2(queue));  // 预期输出：1
    
    // 入队 4
    enqueue2(queue, 4);
    
    // 连续出队
    printf("出队 = %d\n", dequeue2(queue));  // 预期输出：2
    printf("出队 = %d\n", dequeue2(queue));  // 预期输出：3
    printf("出队 = %d\n", dequeue2(queue));  // 预期输出：4
    
    freeQueueWithTwoStacks(queue);
}

// 主函数
int main() {

    printf("\n测试两个栈实现的队列：\n");
    testQueueWithTwoStacks();
    
    return 0;
}